How to ssh to localhost without password?

EDIT: Putting exactly what was done

I need to SSH localhost without password, the usual way of doing it (with public keys) do not work.

user@PC:~$ rm -rf .ssh/*
user@PC:~$ ssh-keygen -t rsa > /dev/null 
Enter file in which to save the key (/home/user/.ssh/id_rsa): 
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
user@PC:~$ ls .ssh/
id_rsa  id_rsa.pub
user@PC:~$ ssh-copy-id -i localhost 
The authenticity of host 'localhost (::1)' can't be established.
RSA key fingerprint is f7:87:b5:4e:31:a1:72:11:8e:5f:d2:61:bd:b3:40:1a.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added 'localhost' (RSA) to the list of known hosts.
user@localhost's password: 
Now try logging into the machine, with "ssh 'localhost'", and check in:

  .ssh/authorized_keys

to make sure we haven't added extra keys that you weren't expecting.

user@PC:~$ ssh-agent $SHELL
user@PC:~$ ssh-add -L
The agent has no identities.
user@PC:~$ ssh-add 
Identity added: /home/user/.ssh/id_rsa (/home/user/.ssh/id_rsa)
user@PC:~$ ssh-add -L
ssh-rsa ...MY KEY HERE

user@PC:~$ ssh-copy-id -i localhost 
user@localhost's password: 
Now try logging into the machine, with "ssh 'localhost'", and check in:

  .ssh/authorized_keys

to make sure we haven't added extra keys that you weren't expecting.

user@PC:~$ ssh localhost echo 'testing'
user@localhost's password: 

user@PC:~$ 

So as you can see in the last command it is still asking the password! How can I fix that? Ubuntu-10.04, OpenSSH_5.3p1

EDIT2:

Adding some info about the sshd

user@PC:~$ cat /etc/ssh/sshd_config | grep Authentication
# Authentication:
RSAAuthentication yes
PubkeyAuthentication yes
RhostsRSAAuthentication no
HostbasedAuthentication no
# Uncomment if you don't trust ~/.ssh/known_hosts for RhostsRSAAuthentication
ChallengeResponseAuthentication no
# PasswordAuthentication yes

EDIT3: Ading result from $ssh -vv localhost

$ssh -vv localhost
...
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Trying private key: /home/user/.ssh/identity
debug1: Offering public key: /home/user/.ssh/id_rsa
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey,password
debug1: Trying private key: /home/user/.ssh/id_dsa
debug2: we did not send a packet, disable method
debug1: Next authentication method: password
user@localhost's password: 

Solution 1:

I did following 3 steps to create the password less login

1. ssh-keygen -t rsa
Press enter for each line 
2. cat ~/.ssh/id_rsa.pub >> ~/.ssh/authorized_keys
3. chmod og-wx ~/.ssh/authorized_keys 

Solution 2:

Have discovered the problem.

Running the server with debuging:

$sshd -Dd

I found it was not able to read the auth_key

$chmod 750 $HOME

Fixed it.

Solution 3:

Another possible answer: the authorized_keys file may exist and be readable. But if it is group- or world-writable, it will still prompt for the password. The answer to THAT problem is

chmod og-wx ~/.ssh/authorized_keys

Solution 4:

Two simple steps:

ssh-keygen -t rsa <Press enter for each line>
ssh-copy-id localhost

Enter password and you're done.