Firstly, I know that this question has been asked a million times, and I have read everything I can find and still cannot fix the problem.

i am encountering this issue when ssh'ing in from my mac to my Ubuntu server on a fresh install of Ubuntu (I reinstalled because of this issue).

I have SSH portmapped to 7070 because my ISP is blocking 22.

On the client:

bash: ssh -p 7070 -v [email protected]
debug1: Reading configuration data /etc/ssh_config
debug1: Connecting to address.org port 7070. 
debug1: Connection established. 
debug1: identity file /home/me/.ssh/identity type -1
debug1: identity file /home/me/.ssh/id_rsa type 1
debug1: identity file /home/me/.ssh/id_dsa type -1
ssh_exchange_identification: Connection closed by remote host

Here's what I have done to try to resolve the issue:

Made sure my maxstartups is ok:

bash: grep MaxStartups /etc/ssh/sshd_config
#MaxStartups 10:30:60

• Made sure hosts.deny is clear of denials.
• Made sure hosts.allow has my client IP.
• Clear out known_hosts on client
• Changed ownership of /var/run to root
• Made sure etc/run/ssh is
• Made sure /var/empty exists
• Reinstall openssh-server
• Reinstall ubuntu

When I run telnet localhost, I get this:

telnet localhost
Trying ::1...
Trying 127.0.0.1...
telnet: Unable to connect to remote host: Connection refused

When I run /usr/sbin/sshd -t

Could not load host key: /etc/ssh/ssh_host_rsa_key  
Could not load host key: /etc/ssh/ssh_host_dsa_key  

When I regenerate the keys with

ssh-keygen -t rsa -f /etc/ssh/ssh_host_rsa_key  
ssh-keygen -t dsa -f /etc/ssh/ssh_host_dsa_key  

I get the same error.

I am pretty sure this is the issue. Can anyone help?