Vagrantを1.8.5にアップデートし、vagrant upをしたら、default: Warning: Authentication failure. Retrying...というエラーの後で、time outになるエラーに遭遇した。
以下のissueに答えが書いてあった。
・Authentication failure after inserting new key with Vagrant 1.8.5. [PATCH]
Vagrant 1.8.5によるエラーだったようなので、1.8.4にすることで解決した。