ssh connect over internet (kali to kali)

Hey Guys,

please help me out before i'm getting nuts at this.
Tried to establish a connection to a friends kali host but cant make it to authentificate. Here are the host details:
Both running Kali 1.1.10 amd64 (up to date metapackage 'kali-linux-full' installed)
Both running under root user. Both have same internal hostname (kali)

What i told him to do
mkdir -p /tmp/original_keys
mv /etc/ssh/ssh_host_* /tmp/original_keys
dpkg-reconfigure openssh-server
service ssh start

Add port forwarding to router

Then I tried to connect: ssh -v -p xxx [Public IP]
Failed with Permission denied (publickey)

So i generate keypair on my host site via ssh-keygen -t rsa
Tar the /root/.ssh folder and send it via crypted Mail to him.
He, of course, extract, check file permission and restart ssh service.
Same error

At last i tried to enable HostbasedAuthentification in /etc/ssh/sshd_config but i'm honest that I dont really got what this is about. Just saw in verbose that ssh tried to proceed with it and failed because Server has bot enable it.

So please, tell me how stupid I am.. I gave up here