Putty erkennt plötzlich keinen Privaten Key

exakt das würde ich als Erstes prüfen, wenn möglich ;)

- Gibt es Fehlermeldungen seitens Putty?
Interessant ist halt die Frage, ob das Passwort Client-seitig oder Server-seitig verlangt wird.
Der Client könnte danach fragen, weil der priv Key es verlangt (s.u.), also noch bevor die SSH-Verbindung überhaupt zustande kommt.
Der Server könnte es verlangen, weil es dort in den sshd-Einstellungen so hinterlegt ist.

- Könnt ihr mit ssh von einer Kommandozeile zugreifen?
Falls ja:
"v" = "verbose", also geschwätzig -> das gibt mehr Infos über den Verbindunsaufbau aus und schmeißt ggf. Hinweise, an exakt welcher Stelle etwas nicht klappt.

- Habt ihr die Möglichkeit, direkt an die Maschine zu gehen?
Falls ja:
einsehen, ob auch dort (noch) alles korrekt ist

Und auch die
überprüfen, ob dort (noch) der entspr. Key hinterlegt ist.

Vermutung: Der Key wurde ausgetauscht / erneuert, und auch wenn der (neue) Key an sich korrekt funktioniert, KANN man SSH-Schlüsselpärchen erstellen, bei denen trotzdem die Eingabe eines Passworts erforderlich ist (oder man überspringt bei der Erstellung eben diese Eingabe, dann ist das Passwort blank, also eine Eingabe nicht nötig).