With that behavior you need to look at the starting circuit. The fuel injection relay has no play in the starter engagement.

A starter is a very expensive place to begin tossing parts at the problem. People more electrically inclines will perhaps have an approach to suggest.

Personally I would begin by performing some normally neglected maintenance items. Remove, clean, and grease the battery connections. Clean the connections at the battery including the small wire that feeds the 12v to the solenoid.

If you have a situation where you have a helper and meter (or test light) handy you might check the 12v to the solenoid while the key is still in the start position but after the starter has stopped spinning.

Good luck,
Randy