If you're positive that this issue started after the starter was replaced, then logic says you got a less than 100% unit. After it clicks and doesn't spin the first time, crawl under and tap on the starter with a hammer while a helper turns and holds the key in the start position for about a 5 count. Do not strike very hard as gear reduction starters don't like the magnet being beaten up. If it turns over after a tap or two, then replace the starter.

Also, it's a good idea to replace the electrical portion of the ignition switch, especially if it's never been done and the part is original. It's a prime culprit for voltage drops which lead to sluggish starts and other weird issues. It's relatively inexpensive and an aftermarket part will work fine.