Solution:
Unix key fingerprints are printed out by the SSH client the first time you connect (or the first time after you delete a host key on the client). The Arizona host keys are the same as the existing Hats keys.

The keys are:

• Arizonas/Hats RSA: ab:62:85:30:20:81:68:a2:7b:df:a2:72:6e:8f:92:a0
• Arizonas/Hats DSA: cd:02:e9:d3:a2:5d:71:d0:63:da:8e:b5:6b:37:bc:f2

The fingerprints for the Arizonas and Hats are:

• xokag-tavib-sibeg-ramyc-vyvag-cusel-gysod-dyduz-zebev-cotyl-nuxix

Arizona users connecting to yuma/phoenix after 9:00 a.m. on January 30, 2006 will see the following message the first time they connect. This does not indicate a security problem, but is due to the changing of the ssh keys on the Arizonas.

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

@ WARNING: 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 the host key has just been changed. Please contact your system administrator.
Add correct host key to "/u/ck/.ssh2/hostkeys/key_22_yuma.pub" to get rid of this message.
Received server key's fingerprint:
xokag-tavib-sibeg-ramyc-vyvag-cusel-gysod-dyduz-zebev-cotyl-nuxix
You can get a public key's fingerprint by running
% ssh-keygen -F publickey.pub on the keyfile.
Agent forwarding is disabled to avoid attacks by corrupted servers.
X11 forwarding is disabled to avoid attacks by corrupted servers.
Are you sure you want to continue connecting (yes/no)? yes
Do you want to change the host key on disk (yes/no)? yes
Agent forwarding re-enabled.
X11 forwarding re-enabled.