I remember losing Google Authenticator data when I had to format my phone. This was years back and didn't have too many accounts setup. With Aegis I have an offline encrypted backup of all my 2FA codes so this is no longer a possibility. Before Aegis I was tempted to use Authy before I had to wait 24hrs to gain my access back after I reset my phone.
2FA on Android has always sucked (lazily created; app data CANNOT constitute and/or subsitute device trust). I wish I had got on to Aegis earlier.