The other option will be to generate a new key pair on the new device, and then add the public key to an account via an already registered key.
Add key for <user@website> at <utcmillisecs>: <new_public_key_goes_here>;<sign>
Add key for <user@website> at <utcmillisecs>: <new_public_key_goes_here>;<sign>
Again, having a command ("Add key ..." as in parent message) for this would make this feature accessible to password/key managers.