Ssh between servers - No DSA host key is known

It seems I can do ssh <IP> but not ssh <hostname>

If I try to ssh to hostname I get the error - No DSA host key is known for host1 and you have requested strict checking.
Host key verification failed.

Where do I set up the DSA keys? Is it ssh_known_hosts?

Assume afterwards I can ssh-keygen and copy the public key back as authorized_keys to allow passwordless access?

---------- Post updated at 12:21 PM ---------- Previous update was at 12:05 PM ----------

OK. Think I sorted the DSA host key issues. So now on host_A, as user_A, I ran:-

ssh-keygen -t rsa
copied id_rsa.pub to host B (user_A/.ssh directory) and rename it to authorized_keys

So going back to host A, ssh user_A@host_B

Still prompts me for password?

Post the full output of ssh -vvv user_A@host_B .

Check the permissions on the target user's home directory (755), .ssh directory (700) and authorized_keys file (600).

home directory is 744.
.ssh is 644.
authorized_keys is 700.

---------- Post updated at 04:30 AM ---------- Previous update was at 04:27 AM ----------

noc1423nm# ssh -v tmauser@drc1423nm
Sun_SSH_1.1.3, SSH protocols 1.5/2.0, OpenSSL 0x0090704f
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Rhosts Authentication disabled, originating port will not be trusted.
debug1: ssh_connect: needpriv 0
debug1: Connecting to drc1423nm [10.0.112.51] port 22.
debug1: Connection established.
debug1: identity file /export/home/tmauser/.ssh/id_rsa type 1
debug1: identity file /export/home/tmauser/.ssh/id_dsa type -1
debug1: Remote protocol version 2.0, remote software version Sun_SSH_1.1.3
debug1: match: Sun_SSH_1.1.3 pat Sun_SSH_1.1.*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-Sun_SSH_1.1.3
debug1: use_engine is 'yes'
debug1: pkcs11 engine initialized, now setting it as default for RSA, DSA, and symmetric ciphers
debug1: pkcs11 engine initialization complete
debug1: Failed to acquire GSS-API credentials for any mechanisms (No credentials were supplied, or the credentials were unavailable or inaccessible
Unknown code 0
)
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client blowfish-cbc hmac-sha1 none
debug1: kex: client->server blowfish-cbc hmac-sha1 none
debug1: Peer sent proposed langtags, ctos: i-default
debug1: Peer sent proposed langtags, stoc: i-default
debug1: We proposed langtags, ctos: i-default
debug1: We proposed langtags, stoc: i-default
debug1: Negotiated lang: i-default
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: Remote: Negotiated main locale: C
debug1: Remote: Negotiated messages locale: C
debug1: dh_gen_key: priv key bits set: 143/320
debug1: bits set: 1595/3191
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'drc1423nm' is known and matches the DSA host key.
debug1: Found key in /etc/ssh/ssh_known_hosts:7
debug1: bits set: 1632/3191
debug1: ssh_dss_verify: signature correct
debug1: newkeys: mode 1
debug1: set_newkeys: setting new keys for 'out' mode
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: newkeys: mode 0
debug1: set_newkeys: setting new keys for 'in' mode
debug1: SSH2_MSG_NEWKEYS received
debug1: done: ssh_kex2.
debug1: send SSH2_MSG_SERVICE_REQUEST
debug1: got SSH2_MSG_SERVICE_ACCEPT

|-----------------------------------------------------------------|
| This system is for the use of authorized users only.            |
| Individuals using this computer system without authority, or in |
| excess of their authority, are subject to having all of their   |
| activities on this system monitored and recorded by system      |
| personnel.                                                      |
|                                                                 |
| In the course of monitoring individuals improperly using this   |
| system, or in the course of system maintenance, the activities  |
| of authorized users may also be monitored.                      |
|                                                                 |
| Anyone using this system expressly consents to such monitoring  |
| and is advised that if such monitoring reveals possible         |
| evidence of criminal activity, system personnel may provide the |
| evidence of such monitoring to law enforcement officials.       |
|-----------------------------------------------------------------|

debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive,hostbased
debug1: Next authentication method: hostbased
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive,hostbased
debug1: Authentications that can continue: gssapi-keyex,gssapi-with-mic,publickey,password,keyboard-interactive,hostbased
debug1: No more client hostkeys for hostbased authentication
debug1: Next authentication method: password
tmauser@drc1423nm's password: 

---------- Post updated at 04:31 AM ---------- Previous update was at 04:30 AM ----------

Got a feeling some of my problems are caused by the fact that these servers were built from flar images of the original ones but with the hostname changed. Hence, some of these ssh files have got the old hostname in.

Is there any way to totally reset ssh and reconfig the whole lot - so it picks up correct hostname?