Annually the SCS Linux Network hosts are upgraded, and the ssh-keys will no longer match. If you know that the server has been upgraded and your ssh-keys no longer match, then it will be safe to accept the new ssh key. Your system administrator will be able to confirm if this is due to a legitimate server upgrade or if it is a ‘man in the middle attack’.

Linux: Host Identification has changed ERROR

In Linux, when a host has changed, it can generate the ‘host identification error’ and the entry can be updated as follows:
ssh-keygen -R <user>@<hostname>
Where <user> is your username and <hostname> is your destination hostname.

No matching key exchange method found ERROR

Some ssh clients may complain about: “Unable to negotiate with port 22: no matching key exchange method found.” 

This is due to the destination server running an old ssh-cypher. Be aware that this may be an insecure connection as the cypher itself is no longer secure. You can try connecting as follows:

ssh -oKexAlgorithms=+diffie-hellman-group1-sha1

You may want to contact the system administrator to inform them of the outdated ssh-server.