Se você tem outra máquina Debian em que confia que tem um conjunto de chaves atual, exporte-os e importe-os em sua nova máquina.
Na sua máquina atual, execute
gpg -a --export >keyring.asc
Na máquina antiga, faça
gpg --import <keyring.asc
Isso adicionará todas as chaves públicas com sua rede de confiança ao computador antigo.
Se você confia no site Debian (criptografado por SSL), você também pode baixar o arquivo de chaves de lá e importe as chaves.