Take a multimeter, set it to DC voltage, stick one lead on the positive battery post (post, not the terminal), and the other on the big starter wire. While cranking the engine, the reading should be very low, .1 of a volt is ideal, but they say up to .4 is acceptable. You can do the same between the negative post and the engine block to test the ground side. This is the only way to effectively load test your connections. If readings are high there is excessive resistance somewhere, corrosion down a cable end, a bad terminal, etc.
If that checks out, the starter may be getting lazy. The bushings and bearings will wear and create a lot of drag.