For the last 2 months, my 2006 Honda Accord I4 Automatic has had trouble starting up, no matter hot or cold starts.

About 25% of the time, it works perfectly - fast cranks and fires up right way.

Sometimes it will crank very slowly and the engine will barely start, but it does start.

Finally, sometimes I will turn the key to the 3 (start) position but will only hear a click. I'll turn it back to 2, then try again and it will work.

A month ago I replaced the battery with one that has more CCA to help with starting. It seemed to solve the issue, but eventually the slow cranks & no cranks came back.

This afternoon, I couldn't get the car started at all for over an hour. Battery voltage was a decent 12.6v, I turned the key, no crank & only a click. I kept doing it and sometimes the starter would turn really, really slowly but die off. When I finally got it to start, it started just like normal, as if it didn't struggle for over an hour to start. That night, I went out to see if it would start, and it started just like normal without issues.

Does anyone know what's wrong with this thing? I suspect it's the starter itself, but it's in such a bad location & expensive so I don't want to proceed with that unless I'm sure. It could be the starter cut relay or ignition switch, but the starter runs perfectly fine sometimes. Below is a circuit diagram of the starting system.