SShd - Could not load host key

Hallo,

ich habe ein Problem mit dem sshd. Ich habe bereits viele Foren, Seiten und Beiträge durchforstet und dennoch muss ich irgendwo einen einfachen Fehler machen.

Mein root Server macht Probleme und zwar bootet er normal bis auf den ssh Server, der möchte nicht starten. Da Webmin installiert ist, kann ich auch eine Fehlermeldung einsehen:

Starting OpenBSD Secure Shell server: sshd
Could not load host key: /etc/ssh/ssh_host_key
Could not load host key: /etc/ssh/ssh_host_rsa_key
Could not load host key: /etc/ssh/ssh_host_dsa_key
Disabling protocol version 1. Could not load host key
Disabling protocol version 2. Could not load host key
sshd: no hostkeys available -- exiting.

Jetzt ist das System im Rescue Modus und ich bekomme das einfach nicht behoben.

Ein ls -l /etc/ssh/ sagt:

-rw------- 1 root root 863 Jul 1 11:36 /etc/ssh/ssh_host_dsa_key
-rw-r--r-- 1 root root 732 Jul 1 11:36 /etc/ssh/ssh_host_dsa_key.pub
-rw------- 1 root root 863 Jul 1 11:36 /etc/ssh/ssh_host_key
-rw-r--r-- 1 root root 732 Jul 1 11:36 /etc/ssh/ssh_host_key.pub
-rw------- 1 root root 928 Jul 1 11:36 /etc/ssh/ssh_host_rsa_key
-rw-r--r-- 1 root root 350 Jul 1 11:36 /etc/ssh/ssh_host_rsa_key.pub

Desweiteren habe ich versucht die Keys neu zu generieren mit:
ssh-keygen -t dsa -P "" -f /etc/ssh/ssh_host_key
chmod 644 /etc/ssh/ssh_host_key.pub
chmod 600 /etc/ssh/ssh_host_key
ssh-keygen -t dsa -P "" -f /etc/ssh/ssh_host_dsa_key
chmod 644 /etc/ssh/ssh_host_dsa_key.pub
chmod 600 /etc/ssh/ssh_host_dsa_key
ssh-keygen -t rsa -P "" -f /etc/ssh/ssh_host_rsa_key
chmod 644 /etc/ssh/ssh_host_rsa_key.pub
chmod 600 /etc/ssh/ssh_host_rsa_key

Ebenfalls kein Erfolg.

In der sshd_config ist folgender Pfad zu den HostKey Files eingetragen:
# HostKey for protocol version 1
HostKey /etc/ssh/ssh_host_key
# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key

Trotz dieser Tatsachen möchte das System einfach nicht richtig starten. Was mache ich falsch bzw. habe ich vergessen?

Zusätzlich ist mir aufgefallen das die Dateien komisch aussehen. Ist folgendes Format richtig?

cat ssh_host_key:
---- BEGIN SSH2 ENCRYPTED PRIVATE KEY ----
Subject: root
Comment: "1024-bit dsa, root@grml, Thu Jul 01 2010 11:36:31 +0200"
P2/56wAAAgIAAAAmZGwtbW9kcHtzaWdue2RzYS1uaXN0LXNoYTF9LGRoe3BsYWlufX0AAA
[...]
---- END SSH2 ENCRYPTED PRIVATE KEY ----

Ich dachte immer diese Datei sieht so aus:
ssh-rsa ...schlüssel.....

Falls ich recht habe, warum wird diese trotzdem so generiert?

Vielen Dank für Eure Hilfe im voraus.

Gruß,
David