I was thinking the other day that just a revoke event that suggests a new key could work.
Clients would then prompt and give notice that the key has been revoked and suggest moving to the new key while providing additional information.
A client could use their own follow graph for additional verification.
For example, Bob and Carol know each other well, Alice follows both of them. Bob revokes his key and suggests a new one. Alice's client notices Carol now follows Bob's new key and displays it in the prompt to switch. Alice then follows Bob's new key.