If I lose my phone, I expect my new phone to have proper continuity on the messages. I'd rather have that than any encryption, to be honest. I don't care if the government spies on me. I do care if something someone sent me gets lost.
Then don't use a messenger that promises end-to-end encryption. Client side encryption is all about ensuring only clients that hold private keys can read messages delivered to them.
You should at least have a backup of your private key so you can import it on your new phone rather than having the sender re-encrypt to whatever key your new phone decides to generate.
