@Rj Musawir Shah
Thank you for your post!
Adding Authenticator to your new device doesn't automatically remove the app from your old device. Even deleting the app from your old device isn't enough. You must both delete the app from your old device AND tell Microsoft or your organization to forget and unregister the old device.
- To remove the app from a device using a personal Microsoft account. Go to the two-step verification area of your Account Security page and choose to turn off verification for your old device.
- To remove the app from a device using a work or school Microsoft account. Go to the two-step verification area of either your MyApps page or your organization's custom portal to turn off verification for your old device.
For more info -https://learn.microsoft.com/en-us/azure/active-directory/user-help/user-help-auth-app-faq#lost-device
If you have any other questions, please let me know.
Thank you for your time and patience throughout this issue.
----------
Please remember to "Accept Answer" if any answer/reply helped, so that others in the community facing similar issues can easily find the solution.