I think it's time for you to find a new phone then. I never know a phone that does that. Are you sure you don't modify something and install something like "deepfreeze" for your phone?
Pretty sure the backup failed or got corrupted. If you can't buy a new phone then I think using another authenticator client might be a good alternative. You should do it asap to make sure you don't lose your access to those exchanges, which will take a very long time to recover.
I did buy a new phone. I went from an LG G4 running Android 6.0 to a Samsung Galaxy 515M (7 amp battery) running Android 10.
There is an odd thing though. After I knew that my Authenticator wasn't working any more I tried redoing my 2FA setup, obviously not knowing what I was doing. Of course that accomplished nothing. But the odd thing is that after rebooting the phone it never again deleted an app. It could just be happenstance, but it is curious. I retained my phone number, so the old phone is still usable for internet access, but it just gathering dust in a drawer.
It was suggested that I use Aegis, but without any Authenticator stuff working there is nothing to try to import to Aegis.