Recht schnell bemerkt man (oder hat vorab bereits gelesen), dass macOS 13 per Default keine RSA-Keys mehr unterstützt. Das musste ich auch feststellen, beim ersten Versuch, mich mit dem SSH-Jump-Server von Mittwald verbinden zu wollen:

$ ssh rXXXX@login.mittwald.de
Unable to negotiate with 185.181.135.131 port 22: no matching host key type found. Their offer: ssh-rsa

Nachdem ich dazu auf den Mittwald-Seiten nichts gefunden hatte, wandte ich mich an den Support:
„Mit macOS13 werden RSA/SHA1 Keys defaultmäßig nicht mehr unterstützt. Der SSH-Jump-Server scheint zur Authentifizierung aber nur ssh-rsa anzubieten. Schade :-(„

Nach 1,5 Tagen bekam ich dann auch eine Antwort:

Wow! Eine derart lösungorientierte Antwort hätte ich nicht erwartet… 🙄

Lösung

Für diejenigen, die eine wirkliche Lösung suchen und sich vom Support erwarten würden:
Ein kleiner Eintrag in die ~/.ssh/config ermöglicht, dass sich moderne Betriebsysteme mit veralteten Servern noch verbinden wollen:

Host login.mittwald.de
  HostkeyAlgorithms +ssh-rsa