This is my thought as well. Keep the "broadcast a notification to all other devices registered to the user" part to verify that the new one is authorized, but i

This is my thought as well. Keep the "broadcast a notification to all other devices registered to the user" part to verify that the new one is authorized, but instead of copying the private key to the new device, tell the server to authorize the newly-generated private key.