Or maybe just do it with a UI, after logging in with the original key. However, That would restrict the user to adding new devices only from trusted machines.

Again, having a command ("Add key ..." as in parent message) for this would make this feature accessible to password/key managers.