Hi, I'm Elise, a fellow user like yourself and I'd be happy to help with your issue.
You would need to setup the Authenticator app from scratch again unfortunately.
If you go to https://account.microsoft.com/ then Security and Additional Security options, you will be able to disable Authenticator. Then you can just set it back up again and register the new phone with it.
Please let me know if you need any further assistance.
Kind Regards,
Elise