When you connect to the service, the client tells the server which public key (key A) its expecting the server to prove that it has ownership of.
If the key A is still valid, the server can use the corresponding private key to sign a challenge.
If the key has been rotated out, the server instead presents the new key, and a signature. Eg, the server responds by naming key B, and presents a certificate of key B, signed by key A (the presented key). Instead of just a single key rotation the server could present a chain of certificates from A to B to C (the key the server wants to use). And optionally, a message saying "from now on, please make further requests using key B as key A has expired".
If the key is compromised, there’s two ways the key can be rotated. Either the key is updated upstream (in the dns record or through an app update or whatever). Or the next request uses the compromised key, (and could be MITMed.) The server responds with the new signed key. And requests after that will be safe.
It’s not perfect - it has some properties from TOFU systems. And it expects the client to cache key material. (It’s not stateless like tls). But I think it would be a pretty workable system.
If the key A is still valid, the server can use the corresponding private key to sign a challenge.
If the key has been rotated out, the server instead presents the new key, and a signature. Eg, the server responds by naming key B, and presents a certificate of key B, signed by key A (the presented key). Instead of just a single key rotation the server could present a chain of certificates from A to B to C (the key the server wants to use). And optionally, a message saying "from now on, please make further requests using key B as key A has expired".