Batteries in PHX tend to fail well ahead of other regions, from the heat.
So if the batteries are longer than 1 summer old, it can be already dead.
12.5V with AC on, at the early part of a trip while the batteries are being charged from starting is not unusual.
FYI, my brand new (high tech) alternator is pulled down to 12.5V right after starting.
However, if after running for 15 minutes --- or longer, and you are still only seeing 12.5V at over 30mph (1,000 rpm), you got a problem.
Have you tested alternator output.