User problems with a changed ssh host key

Background:
aerocom-users.met.no was moved to a new machine, but the hostname was retained. In addition, the operating system was updated from Ubuntu 12.04.5 LTS to Ubuntu 16.04.1 LTS. This upgrade phased out the support for DSA keys for ssh authentication as well as Met Norway IT policy did.
This leads to two possible problems when users try to use aerocom-users.met.no from systems that had used to connect to it before:

Users need to update the ssh host key

Users that used a DSA public key before need to change to a RSA key (and provide the public key)

update the ssh host key

if a user has been connected to aerocom-user.met.no before he/she will see the following error message

jang@pcxyz:~/.ssh$ ssh aerocom-users.met.no
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: POSSIBLE DNS SPOOFING DETECTED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
The RSA host key for aerocom-users.met.no has changed,
and the key for the corresponding IP address 157.249.176.166
is unknown. This could either mean that
DNS SPOOFING is happening or the IP address for the host
and its host key have changed at the same time.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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 RSA key sent by the remote host is
64:58:af:ac:e4:ee:5d:ad:12:01:15:6f:80:76:cc:42.
Please contact your system administrator.
Add correct host key in /home/jang/.ssh/known_hosts to get rid of this message.
Offending RSA key in /home/jang/.ssh/known_hosts:8
remove with: ssh-keygen -f "/home/jang/.ssh/known_hosts" -R aerocom-users.met.no
RSA host key for aerocom-users.met.no has changed and you have requested strict checking.
Host key verification failed.

Reading through the error message, the user is pointed to the solution of the problem: running the following command:

ssh-keygen -f "/home/jang/.ssh/known_hosts" -R aerocom-users.met.no

another possibility is to just remove the offending line from /home/jang/.ssh/known_host. The line number is also told by the error message in the following line:

Offending RSA key in /home/jang/.ssh/known_hosts:8

Removal of (in this example) line 8 of ~/.ssh/known_host with your favourite text editor also solves the problem.

Running the first command outputs the following:

jang@pcxyz:~/.ssh$ ssh-keygen -f "/home/jang/.ssh/known_hosts" -R aerocom-users.met.no
/home/jang/.ssh/known_hosts updated.
Original contents retained as /home/jang/.ssh/known_hosts.old

connecting to aerocom-users.met.no then leads to:

jang@pcxyz:~/.ssh$ ssh aerocom-users.met.no
The authenticity of host 'aerocom-users.met.no (157.249.176.166)' can't be established.
ECDSA key fingerprint is e7:9e:f0:91:70:3b:e3:b8:4e:f7:e8:07:c0:21:1c:de.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added 'aerocom-users.met.no' (ECDSA) to the list of known hosts.
Welcome to Ubuntu 16.04.1 LTS (GNU/Linux 4.4.0-34-generic x86_64)
* Documentation: https://help.ubuntu.com
* Management: https://landscape.canonical.com
* Support: https://ubuntu.com/advantage
System information as of Fri Sep 2 08:46:36 UTC 2016
System load: 0.1 Processes: 197
Usage of /home: 1.6% of 1023.50GB Users logged in: 2
Memory usage: 4% IP address for eth0: 10.20.24.5
Swap usage: 0%
Graph this data and manage this system at:
https://landscape.canonical.com/
Get cloud support with Ubuntu Advantage Cloud Guest:
http://www.ubuntu.com/business/services/cloud
1 package can be updated.
0 updates are security updates.
*** System restart required ***
=========================================================================
INFO
aerocom-users.met.no has moved to a new machine and the aerocom database
has been reorganised
The database can now be found below the directory
/metno/aerocom-users-database
and is then further divided into the projects we work and have worked on
Please write an email to jan.griesfeller@met.no or michael.schulz.met.no
or annac@met.no in case you have further questions
=========================================================================
Last login: Fri Sep 2 08:45:43 2016 from 157.249.112.29
jang@aerocom-users-ng:~$

Please note the the offcial hostname is aerocom-users-ng.met.no

create a new rsa key

Step 1: Check for SSH keys

First, we need to check for existing ssh keys on your computer. Open up Terminal and run:

$ cd ~/.ssh
$ ls
# Lists the files in your .ssh directory

Check the directory listing to see if you have a file named Id_rsa.pub. If you don't, go to step 2. If you already have an existing keypair, skip to step 3. Please note that aerocom-users-met.no will not accept DSA keys. These are considered not secure anymore.

Step 2: Generate a new SSH key

To generate a new SSH key, enter the code below. We want the default settings so when asked to enter a file in which to save the key, just press enter.

$ ssh-keygen -t rsa -C "my comment"
Generating public/private rsa key pair.
...

Enter the path to the file that will hold the key: By default, the file name $HOME/.ssh/id_rsa, which represents an RSA v2 key, appears in parentheses.

Enter file in which to save the key (/home/user/.ssh/id_rsa): <return>

Enter a passphrase for using your key: The passphrase you enter will be used for encrypting your private key. A good passphrase should be alphanumeric having 10-30 character length. You can also use a null passphrase however this can cause a security loophole.

Enter passphrase (empty for no passphrase): <Type the passphrase>

Re-enter the passphrase to confirm it: Type your passphrase once again to confirm it.

Enter same passphrase again: <Type the passphrase>
Your identification has been saved in /home/user/.ssh/id_rsa.
Your public key has been saved in /home/user/.ssh/id_rsa.pub.
The key fingerprint is:
0b:fa:3c:b8:73:71:bf:58:57:eb:2a:2b:8c:2f:4e:37 user@myLocalHost

Step 3: Send your public key to jan.griesfeller@met.no and/or annac.met.no

In the folder ~/.ssh you will find file(s) ending with .pub. Please send us the one you just created e.g. Id_rsa.pub. And no other file

Further information

This page was partly stolen from wikipedia and github.
If you want to know how key authentication works, please read this article about public key cryptography.