Needing to deactivate 2fa to link a new authenticator is one of my big complaints about so many systems. You should be able to pair a new one without removing the old one, or at least have it replace it.