Hace un par de semanas escribía una entrada sobre la caducidad de las claves APT, proponiendo una forma de subsanarlo. Acabo de ver que hay un paquete (fechado a 4 días después de yo haber publicado el artículo) en la rama inestable de debian: debian-archive-keyring que contiene las nuevas claves que yo había explicado como importar y una más para el repositorio de AMD64. Con solo instalar este paquete:
apt-get install debian-archive-keyring
ya te las descarga y te las inserta en el anillo de claves de APT, muchísimo más rápido y sencillo que la otra solución (debían haber puesto este paquete antes de empezar a firmar paquetes con esa clave, digo yo :P).