Test you theory by turning the key to the ON position without trying to start the engine. Does the CD player now continue from the last played track, or go back to track 1? If the former is true, your battery voltage is likely dropping during cranking to the point where memory circuits are compromised. This could be caused by dirty or loose battery terminal connections, or a high impedance cell (common near or at the end of battery life).

I agree with those who suggest, after 5 years of use, a replacement battery would be good insurance.