I have the same issue as you and here is what I can tell you from MY personal experience. I just did this yesterday (and I have done it multiple times in the past as well).
Here is a list of the accounts I have:
Microsoft Account
Google Account
Facebook Account
DropBox Account
GitHub Account
Wildstar-Online (MMO game)
Of the above accounts, the ONLY one I have to remove the authenticator from is the Wildstar-Online account.
All of the remaining accounts, here is what I do.
1. Open a browser window and log into ALL of those accounts and make sure you are authenticated and saved.
-In my case, I have 2 Microsoft and 2 Facebook accounts so I use browsers in Private Sessions or another browser to log into additional accounts
2. Downgrade / Update your phone / Install Updates / Reset your phone after it is all flashed (I do this as a precaution)
3. Once you are back into the OS, log into your primary MS Account on your phone. Have it Email you your security code and verify.
4. Install the Authenticator App
For your MS Account, go to Options > Accounts and Security > Security and Password > Turn Off Existing Apps
Then, you click on Set up and it will walk you through setting it back up.
Google Account, Click on your picture and select Account > Click Security at the top > 2-Step Verification click Settings > Then click Move to a different phone and go through the setup process
Facebook Account, go to Settings > Security > Ne3xt to Code Generator click Edit > Set up and go through the process.
I mean, you can remove them, but I never do as you can recover through other means on larger sites.
Hope this helps!