Abstractly I'm thinking of a situation where there's an authority that houses public keys for users. Say a user goes about using their private key to sign messages but one day finds that their private key has been compromised. Assuming the cause of the original compromise has been fixed (to prevent a second compromise), how can the user publicly indicate not only "Do not use my previous public key" but also "This is my new public key and it can be trusted"?

If the user wasn't compromised then they could publish a signed message saying "Use this new public key" but this is no longer possible because there's no confidence in who signed the message once it's compromised. An Eve could create a new public/private pair and try to coerce people that this new pair is to be trusted, just like the user is trying to do with their new key.

I imagine there could be some sort of Certificate Revocation List but for public keys that a user could add their public key to once they believe they've been compromised. How then could a user re-establish trust with a new key?