Paramiko connect not working due to BadHostKeyException

Question

I am trying to connect to an ssh server using the python paramiko module, but when I connect, I get a BadHostKeyException. Can someone redirect me how to solve this exception.

import paramiko

def checkSSH(host,user,password,command):
    ssh=paramiko.SSHClient()
    ssh.load_system_host_keys()
    ssh.set_missing_host_key_policy(paramiko.AutoAddPolicy())
    ssh.connect(hostname=host, username=user, password=password)
    print ssh.exec_command(command)
    ssh.close()
    return ssh

username='fakeuser'
password='fakepasswd'
ips =  ['2.2.2.2']
response={}
ssh_issue=0
for ip in ips:
        try:
                print ip
                checkSSH(ip,username,password,'date')
        except paramiko.BadHostKeyException as e:
                print str(e)
                #I Need to do something here to get rid of this execption and retry
        except:
                import traceback
                print traceback.format_exc()
                response[ip]='SSH_Needs_Reloading'
                ssh_issue=1