First:

$ ssh-keygen -t dsa -P '' -f ~/.ssh/id_dsa
$ cat ~/.ssh/id_dsa.pub >> ~/.ssh/authorized_keys

Connecting to SSH servers gives this message:

$ ssh -vvv localhost
OpenSSH_5.3p1, OpenSSL 0.9.8m 25 Feb 2010
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to localhost [127.0.0.1] port 22.
debug1: Connection established.
debug1: identity file /home/charlie/.ssh/identity type -1
debug1: identity file /home/charlie/.ssh/id_rsa type -1
debug3: Not a RSA1 key file /home/charlie/.ssh/id_dsa.
debug2: key_type_from_name: unknown key type '-----BEGIN'
debug3: key_read: missing keytype
debug3: key_read: missing whitespace
debug3: key_read: missing whitespace
debug3: key_read: missing whitespace
debug3: key_read: missing whitespace
debug3: key_read: missing whitespace
debug3: key_read: missing whitespace
debug3: key_read: missing whitespace
debug3: key_read: missing whitespace
debug3: key_read: missing whitespace
debug3: key_read: missing whitespace
debug2: key_type_from_name: unknown key type '-----END'
debug3: key_read: missing keytype
debug1: identity file /home/charlie/.ssh/id_dsa type 2
ssh_exchange_identification: Connection closed by remote host

My /etc/hosts.allow is as following:

sshd: ALLOW

/etc/hosts.deny is as following:

ALL: ALL: DENY

I have changed my /etc/ssh/sshd_conf as following:

ListenAddress 0.0.0.0
Protocol 2

# HostKey for protocol version 1
#HostKey /etc/ssh/ssh_host_key
# HostKeys for protocol version 2
HostKey /etc/ssh/ssh_host_rsa_key
HostKey /etc/ssh/ssh_host_dsa_key


RSAAuthentication yes
PubkeyAuthentication yes
#AuthorizedKeysFile     .ssh/authorized_keys

PasswordAuthentication no