I am pretty sure that icloud will backup your phone whenever you have it connected to power and wifi. You will need to restore your phone to a recent backup prior to when you upgraded to the newest version of iOS (and when google authenticator was still working)
Yes that may be true , but thankfully my iCloud is full so it didn't .
So the only way to get the app from iCloud is to restore the whole phone from iCloud backup? I hate apple sometimes...