Searching for a rekeyable scheme for encrypted values

Is there a secure way to compute a deterministic tag token like: secT = Enc(tag, k1) (or a keyed hash), such that when I rotate the key to k2, the client can send a re-key token x and the server can transform existing tokens via: Enc(tag, k2) = f(secT, x) without learning the tag or either key?
the produced values should be deterministic (equality should be the only leakage), and should not be brute-forceable on low-entropy tags. Originally i was going with Hmac but rekeying would force the client to recompute all tags ie decrypt the document, recompute the hmac, reencrypt the document.