Sind Hostnamen bzw. IP-Adressen der beiden Systeme auch identisch?
Hatten die betroffenen Benutzer bereits eine Verbindung zum Server, sodass ~/.ssh/known_hosts einen passenden Eintrag aufweist?
Eine Lösung, die weniger hilfreich klingt, findet sich in der ssh(1) Manpage. Im Abschnitt Authentication wird eine hostweit gültige Datei /etc/ssh/ssh_known_hosts angesprochen, in die du deinen Hostschlüssel eintragen kannst. Das bringt dir natürlich nichts, wenn du dann dreißig Client-Systeme bearbeiten musst. 😉
Eine weitere Möglichkeit sehe ich in SSH-Zertifikaten. Ich habe das noch nicht ausprobiert, allerdings hat es den gleichen Effekt wie die TLS-Zertifikate für Websites: Alle Clients lernen einmal, einer bestimmten Zertifizierungsstelle zu vertrauen. Und sobald ein Host mit passend signiertem Zertifikat auftaucht, wird nicht mehr herumgejammert.
Für das Einrichten der Zertifizierungsstelle musst du zwar wiederum an alle Clients - dafür aber nur noch einmal bzw. einmal alle paar Jahre, je nach Zertifikatslaufzeit des Zertifizierungsstellenzertifikats. Wenn du das für die Clients / Anwender gleich mit machst, kannst du automatisch dafür sorgen, dass die ansonsten nicht ablaufenden öffentlichen Schlüssel in den ~/.ssh/authorized_keys sinngemäß auch ein Ablaufdatum erhalten.
Wie bereits geschrieben, habe ich dazu noch nichts ausprobiert. Hier noch ein Beitrag, der vielleicht hilft: SSH certificates (Medium) 🇬🇧