Se apenas o servidor que contém os pacotes for comprometido e não a chave de assinatura privada, não há muito o que fazer. A chave antiga permanece válida e os pacotes modificados pelo invasor serão detectados como tal. Presumo que a sua pergunta é o que acontece se a chave de assinatura estiver comprometida.
Desde que a chave antiga não tenha expirado, as pessoas continuarão a baixar os pacotes antigos, sem saber que a chave foi comprometida. O ideal é que a ferramenta de gerenciamento de pacotes verifique se a chave não foi revogada (não sei se o apt, o yum e os amigos fazem isso). No entanto, o primeiro passo para responder a um compromisso seria interromper a distribuição de pacotes assinados com a chave antiga e começar a distribuir pacotes assinados com a nova chave. Portanto, qualquer pacote modificado com mal-intencionado permaneceria apenas em espelhos antes de serem atualizados.
Quando as pessoas começam a receber pacotes assinados com a nova chave, elas recebem uma mensagem de erro informando que os pacotes não estão assinados. Esperamos que isso indague o que está acontecendo e tente obter a nova chave.
O compromisso também será anunciado nas listas de discussão de segurança e em vários canais de notícias do setor. Então, se você seguir estes, você será notificado. É claro que você também deve tomar cuidado com isso: um invasor pode comprometer o servidor de lista ou a conta de um desenvolvedor e enviar um aviso de comprometimento de chave falso com uma nova chave pública que, na verdade, é para sua própria chave privada.
Não há mágica para distribuir a nova chave. Você precisa de um canal confiável para distribuir a chave em primeiro lugar, ou mais precisamente para estabelecer confiança na nova chave. Isso é exatamente tão difícil quanto estabelecer confiança na chave antiga. (Em outras palavras, a maioria das pessoas o obterá do site HTTP ou de uma imagem de CD não assinada.) Você pode obter a nova chave em um site HTTPS, se confiar no site (e na CA que fez o certificado do site e o navegador que você está usando e sua base confiável!) não foi comprometida. Ou se você conhece e confia em alguém que tem a chave, você pode perguntar por ela.
Observe que acima, estou usando o "pacote" em um sentido simples, assumindo um modelo simples em que os pacotes são assinados diretamente com a chave de assinatura da distribuição. Na verdade, em algumas distribuições (por exemplo, todas as que usam o APT), o que é assinado são arquivos contendo uma lista de somas de verificação criptográficas de pacotes, e há um processo de dois estágios em que o instalador verifica se o pacote tem a soma de verificação esperada e que a lista tenha a assinatura esperada. O princípio é o mesmo: o invasor que comprometeu a chave injetaria os pacotes mal-intencionados e os arquivos de lista nas somas de verificação dos pacotes mal-intencionados, assinados com a chave comprometida. A resolução requer a restauração dos arquivos de lista e dos pacotes.