Bueno, en todas partes se puede leer al respecto, no voy a teorizar de quien es la culpa, buscar un poco por google y encontrareis... ahora lo importante:

• Hacer un upgrade y luego un dist-upgrade en vuestra/s debian/s; se os instalará tambien el paquete openssh-blacklist que guarda claves conocidas como peligrosas (las de 1024 y 2048) para que no sean permitidas (podeis verlo dentro de /etc/ssh/)
• Leeros estos dos "documentos": http://wiki.debian.org/SSLkeys y http://www.debian.org/security/key-rollover/ (Andaros con ojo que es un wiki, y no todo lo que pone va a misa, más con la de actualizaciones que se han hecho... no hagais copy-paste en la consola, pensad lo que estais haciendo.
• En el caso de ssh, hacer "borron y cuenta nueva" es tan simple como; pese que esto ahora no hace falta ya que se ejecuta como guion con el propio paquete y nos deja como .broken las antiguas.
  

  ~# /etc/init.d/ssh stop
  ~# rm /etc/ssh/ssh_host_*
  ~# dpkg-reconfigure openssh-server
  

  Cuando conecteis desde el cliente os dará un mensaje como este:

  @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  @    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
  @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
  Someone could be eavesdropping on you right now (man-in-the-middle attack)!
  It is also possible that the RSA host key has just been changed.
  [..]
  

  Quitais esa maquina, de vuestro known_hosts y listos.

• Para el resto miraros (como mínimo) el primer enlace que se os he indicado y mirar las "concreciones" de cada uno de vuestros demonios, y ejecutables que estéis utilizando. Por ejemplo cuidado con lo que hacéis con las llaves de los DNS's, que podeis dejar los secundarios sin actualizar zonas... Lo que he dicho, seguir instrucciones, pero miraros lo que estais haciendo...
• Encontrareis útil ssh-vulnkey que sirve para comprobar

• Si utilizas algo de esto (esta casacado de la docu oficial de los dos enlaces), leetela... algunos explica incluso cosas como "no se si esto le afecta..." es una documentación muy "live"... tenerlo en cuenta (en el enlace de key-rollover, esta un poco mejor explicado):
  
1. Asterisk
2. BIND9
3. boxbackup
4. Cfengine
5. courier imap/pop3
6. uw-imapd
7. cryptsetup
8. csync2
9. cyrus imapd
10. dovecot
11. dropbear
12. exim4
13. ftpd-ssl
14. Generic PEM Generation
15. gitosis
16. OpenSSH (Server)
17. OpenSSH (Client)
18. OpenSWAN
19. StrongSWAN
20. OpenVPN
21. postfix
22. puppet
23. ssl-cert
24. telnetd-ssl
25. tinc
26. Tor Onion Router / Hidden Service Keys
27. encfs
28. xrdp
29. Kerberos (MIT and Heimdal)
30. pwsafe
31. slurm-llnl
32. Nessus