I know similar questions have been asked many times, but there's a difference here:
Trying to ssh to the server I get:
$ ssh cl11lx
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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 a host key has just been changed.
The fingerprint for the ECDSA key sent by the remote host is
07:51:03:4e:5e:ba:e8:44:70:77:cb:57:78:57:59:35.
Please contact your system administrator.
Add correct host key in /nethome/ajalali/.ssh/known_hosts to get rid of this message.
Offending RSA key in /var/lib/sss/pubconf/known_hosts:8
remove with: ssh-keygen -f "/var/lib/sss/pubconf/known_hosts" -R cl11lx
ECDSA host key for cl11lx has changed and you have requested strict checking.
Host key verification failed.
The most relevant question I found is here, which is closed as a duplicate of this one which itself is closed as off-topic. But they're not the same anyway. Another related question is asked here.
In most cases, as we know, you can fix the problem by replacing the server key, for example by running:
ssh-keygen -R <host>
But neither this solution, nor removing the offending key from the file /var/lib/sss/pubconf/known_hosts
did solve my problem.
As soon as I remove that whole file, or remove the offending key, the key is back.
Please note that all my systems are members of a freeipa server, which itself is an LDAP/Kerberos on the backend.