vagrant 1.8.5 ssh failures!

Vagrant 1.8.5 throws the below error when doing a vagrant up

default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
Timed out while waiting for the machine to boot. This means that  
Vagrant was unable to communicate with the guest machine within  
the configured ("config.vm.boot_timeout" value) time period.

If you look above, you should be able to see the error(s) that  
Vagrant had when attempting to connect to the machine. These errors  
are usually good hints as to what may be wrong.

If you're using a custom box, make sure that networking is properly  
working and you're able to connect to the machine. It is a common  
problem that networking isn't setup properly in these boxes.  
Verify that authentication configurations are also setup properly,  
as well.

If the box appears to be booting properly, you may want to increase  
the timeout ("config.vm.boot_timeout") value.  

Solution:
Add config.ssh.insert_key = false to the Vagrantfile