Sorry to hear that!
This seems to be my normal experience with a new phone for MFA apps. I’m doing something wrong. That and setting up email are so dreaded that I hold off updating.
… Yeah I'm not sure that's very good for a 2FA app either. Offline backups feel better for me. I use something else for 2FA.
If it's a MFA I actually don't care much about (security-wise), I simply save the token on bitwarden so it autocompletes for me (it defeats most of the main point of "multi" FA but I don't care about it to begin with).
Printing is not a bad idea, especially for backup, if you put them in a fire-proof safe or something. Make sure to give each a name to know which service they are for.
I've been burned too many times.