This seems to have changed recently. You can now remove the phone as soon as you add authenticator as an option.