Oh that's fantastic Microsoft Authenticator requires those accounts to be handled one by one which means I need to go through 20 different accounts to re-done MFA setup as I got a new phone now.
As a solution, I went into https://mysignins.microsoft.com/security-info as described, clicked on "Add sign-in method" but this time I clicked on "I want to use a different authenticator app" and used Google Authenticator. So next time when I got a new phone, I will know the transition will be smoother !