This is just me spitballing, but maybe its only necessary to have an event type that says "this key is compromised" then its up to the client/user to find the new pubkey through their social circle.

Then maybe there could be a new kind of event that would be published by anyone which would say "X's new key is Y". then the client could gather these events from your followers or random strangers? and show the user a few options (hopefully just one) for a new pubkey to follow. almost like a social voting system? idk