Thanks for your question.
When changing your device, the process with authenticator is to backup your accounts.
If this was not done, for work accounts you will need to contact your organizations IT admin to help re-register you for MFA to resolve this for your work accounts.
Them doing this will re-register you for MFA and you will need to re-enroll.
For product accounts like facebook you will need to contact their support team as well.
You can mark it 'Accept Answer' and 'Upvote' if this helped you
Regards,
Abiola