As long as you use encrypted backups with iPhone, your GA keys are backed up and you can restore a new phone with them also.
I also switched to OTPAuth, great app, provides encrypted backups and switching to a new phone was seamless. Would absolutely recommend over Google Authenticator.