A estratégia para isso no lado unix das coisas seria manter as antigas e novas cópias da chave no keytab do serviço. O Kerberos mantém os números de versão nas chaves e as bibliotecas do kerberos verificarão o keytab da versão correta a ser usada quando o ticket de serviço for apresentado.
Você só pode ter uma versão da chave no KDC, mas enquanto as versões antigas e novas da chave estiverem no keytab do servidor, seus clientes não verão interrupção no serviço. Se você puder explicar como instala o keytab para o serviço, provavelmente posso sugerir algo.