A new battery is frequently the cause for a lot of problems related to starting and low-rpm operation. It is still worthwhile to check out the current draw during starting using a DC clamp-on ammeter over one of the battery leads. (You don't need to access the starter itself for this.) Sometimes a new battery's ability to supply additional current without severe voltage drop can temporarily mask the effects of a failing starter motor.
Given that your battery is eight years old, it seems likely to be the root cause, but I would not ignore other possible issues.
While that may be "normal" in a hot climate, I have always done much better where I live. I never use a battery tender other than for an hour or two a couple of times during our typical four month winter layoff. While we get moderately hot weather in the summer, it does not approach what you see in Phoenix. On the two Gen II FJRs I have owned, I got 10 years and about 240,000 km (150,000 miles) out of the OEM battery in my '07 and 12 years and 160,000 km (100,000 miles) on the 2011 OEM Yuasa - I bought the '11 when it was already 7 years old but with only 36,000 miles.
Even here, that is better than most. Some luck, but I am very careful to avoid deep discharge or overcharging. I have never been convinced that the regular use of a battery maintainer does anything to extend a battery's lifetime. In fact, one that isn't properly regulated or one that isn't compensated for ambient temperature can do more harm than good.