Google authenticator is close source app, this is one of the reasons you suppose not to use it because you can not know if there is any vulnerability running such as spyware, using close source apps or software should be completely discouraged. There are reputed and recommended open source authenticators which will be better for you to use.
Recommended and reputed authenticators
Aegis and andOTP are open source, this is one of the reasons you should use it, the source code is available to the public, any vulnerability found will easily be known and be fixed. But also you can make use of password to protect it on your device, unlike Google authenticator that can be easily accessed without no password protection.
How do I go about recovery public keys and how do I go about store it again???Any solution my problem?
It depends.
If you do not have access to your old device and you do not do any backup, it will be impossible for you to recover back the authenticator, that is why proper backup is necessary.
If you still have your old device with you, that will make this faster.
- open the Google authenticator
- click at the three dots on the upper right side
- click on transfer accounts
- click on export accounts
- input the password of your device
- make sure all the site authentication you want to export are marked (they are all marked by default, but you can unmarked the ones you do not want to import to your new device)
- click on 'next'
You will see a QR code, import it to the Google authenticator on your new device, all the sites you enabled authentication that you marked while exporting it to new device will appear. You can also do the backup of this QR code in case of recovery. But, I will still advice you to use open source authenticators like Aegis and andOTP.