In version 1 of the SSH protocol, the server has a RSA key (always) and the client asymmetrically encrypts a random blob with the server's public key. The random blob is then used as basis for the session key which will be used to encrypt the data.
In version 2 of the SSH protocol, client and server use Diffie-Hellman (or an elliptic curve variant thereof) to established a shared session key. The server signs his half of the protocol with his key, which might be RSA or DSA.
While RSA encryption and RSA signature can both use the same kind of mathematical object (a "RSA key"), they are nonetheless distinct algorithms. The SSHv2 way additionally offers Perfect Forward Secrecy, which is good (if someone steals the server's key, he can decrypt past SSHv1 connections that he recorded, but not so with SSHv2 connections).
In the SSH model, the client makes sure that it talks to the right server by remembering the public key of each server (that's the
.ssh/known_hosts file). When it encounters a new key (a server to which the client never connected yet), it wants to display something which the human user may use to confirm that the public key from the server is genuine. The fingerprint is a hash value; the user is then supposed to phone the intended server's sysadmin, to dictate the fingerprint and get confirmation that's it is the right one.
The "random art" is a visualisation of the fingerprint in a way which is supposed to be easily remembered by a human eye & brain. The idea is that the user first memorizes the "art" associated with the server, and later on visually checks that the recomputed "art" is the same. (Intended scenario: being able to use random client machines while travelling.)
Personally I prefer to learn by heart the fingerprint; at least I can compute the success probability of the attacker. Better yet, I travel with my own device, which at least should be less virus-ridden than a random machine from an Internet café.