Store a key id with every ciphertext so several keys can coexist. After a leak, rotate first (the old key is compromised), then clean up.