The only people you have to declare your newly rotated key to is: Your followers ∩ The ones you want to keep.

User applications would have the option of caching keys used for historic notes. The local cache might get a bit chunky if users rotate a key for each note, but keys could be locally jettasoned using a stack-height setting for each chain of keys [user].

One of the reasons I don't like Nostr is that there is no reliable way to expunge notes from relays. Without the ability to do this, there doesn't seem to be a way to meet conditions for acceptable levels of privacy.