First of all I know this is a duplicate issue but I battled with this issue for about 20 hours as none of other questions's answers were working for me. This is Mac OS X specific question and answer. Virtual provider was VirtualBox 4.3 and 5.0. Vagrant versions 1.7.1 and 1.7.4
This SSH authentication failure kept on happening. If I waited or exited the process I could "vagrant ssh" in without problems, using default password "vagrant". But because this SSH failure happened, it meant that the after boot -scripts were not executed either.
vagrant up
Bringing machine 'default' up with 'virtualbox' provider...
==> default: Importing base box 'laravel/homestead'...
==> default: Matching MAC address for NAT networking...
==> default: Checking if box 'laravel/homestead' is up to date...
==> default: Setting the name of the VM: homestead
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
default: Adapter 1: nat
default: Adapter 2: hostonly
==> default: Forwarding ports...
default: 80 => 8000 (adapter 1)
default: 443 => 44300 (adapter 1)
default: 3306 => 33060 (adapter 1)
default: 5432 => 54320 (adapter 1)
default: 22 => 2222 (adapter 1)
==> default: Running 'pre-boot' VM customizations...
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
default: SSH address: 127.0.0.1:2222
default: SSH username: vagrant
default: SSH auth method: private key
default: Warning: Connection timeout. 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...
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...
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.
Vagrant 1.7 has this default config set to true: config.ssh.insert_key
Vagrant will automatically insert an keypair to use for SSH, replacing the default Vagrant's insecure key inside the machine if detected. link to Vagrant SSH settings
When after vagrant up I did vagrant ssh-config I could see that the private key path was ~/.vagrant.d/insecure_key – but that key was not copied to inside VM either.
The problem was in that I had somehow messed up my OS X's SSH config. This was apparent when I ran command ssh-add -l to list loaded keys in SSH agent. There was two different keys with the same path! However I cannot confirm this was the main reason for the problem as it had persisted for several days and during which I had made a few reboots.
I made a backup of .ssh folder and copied old config lines and files one by one. Another thing I did was to remove this ill-advised tip to add this line in ~/.ssh/config
Host *
ForwardAgent yes
This practice is strongly recommended against by Github:
Warning: You may be tempted to use a wildcard like Host * to just apply this setting to all SSH connections. That's not really a good idea, as you'd be sharing your local SSH keys with every server you SSH into. They won't have direct access to the keys, but they will be able to use them as you while the connection is established. You should only add servers you trust and that you intend to use with agent forwarding.
Before doing these steps I emptied ~/.vagrant.d folder to make sure I had no previously set up global configs in play. You could also uninstall Vagrant with their uninstall script and then reinstall.
Rebooted. Then I created a new SSH key.
Then vagrant provision or vagrant destroy && vagrant up. This is how I finally got this problem solved!