Anupriya A R,
Did you properly backup your old authenticator to from the old phone to the Google (Android) or Apple (iOS) cloud account and then recover that backup to your new phone device as detailed in the following Microsoft documents?
Back up account credentials in Microsoft Authenticator - Microsoft Support
Restore account credentials from Microsoft Authenticator - Microsoft Support
Most consumer users of the Microsoft Authenticator aren't aware of these requirements and so instead they simply install a new copy of the authenticator app on the new phone and set it up from scratch, which obliterates the existing accounts on the old phone and can't work with the new one either, since the credentials in the account itself no longer match.
You're correct that this is a common problem, but it's truly a user education issue and not a technical one, since I've done this process myself the correct way with my personal account and everything from the old authenticator worked immediately on the new phone once it was properly restored.
However, I don't also have a Work or school account, so I don't know how well that portion works with restore, though according to these documents it's supposed to for at least one such account.
Rob