Encontrei o mesmo problema e achei esta página no Google. Felizmente ainda tínhamos a chave disponível localmente em outro servidor. Salve o seguinte em um arquivo de texto percona.key
e importe-o com cat percona.key | sudo apt-key add -
.
[KEY REMOVED] Consulte link para a chave atual.
Espero que isso ajude alguém!