No es necesario cambiar la clave HMAC a menos que crea que se ha comprometido (o por algún otro motivo, desea que los mensajes autenticados bajo la clave anterior ya no se consideren válidos). Suponiendo que use una función hash razonable, firmar "demasiados" mensajes con la misma clave no compromete la clave.
Toda la seguridad de HMAC proviene de que la clave de HMAC se mantiene en secreto, por lo que enviarla en texto sin formato casi seguramente anulará todo el propósito de usar HMAC en lugar de solo un hash público sin clave. Si necesita poder cambiar las claves, es posible que desee confiar en la criptografía asimétrica (clave pública), aunque no ha dicho lo suficiente sobre su aplicación para que sea posible una recomendación más específica.