The solution should involve revoking the compromised key and linking it to the new one. Clients would then display notes from the old key up to the revocation point, and from the new key thereafter. If your key is compromised, revoke it and establish a link to the new one. Clients could follow the new key automatically or manually—it doesn't matter.
Discussion
In this scenario who runs the key registries and how do you trust registry A vs B?
Why use registries? Just broadcast a revocation event to as many relays as possible. Key revoked.
If I steal your key and revoke it what happens then?
you saved me time by doing what i needed to do.
I control the key too and just tell everyone to follow my new account. You do the same. How is this resolved?
The same way as people identified you in the first place. Someone that knows IRL you can confirm your identity, or use nip05 to verify, or another social media, telegram, email, phone, whatever.