paramikoの調子が悪かったので再インストールしようとしたところ、
Collecting paramiko
  Using cached paramiko-1.16.0-py2.py3-none-any.whl
こんな感じでキャッシュを使ってインストールされるため、症状が改善しませんでした。

こういう場合は、一旦該当のパッケージをアンインストールした後で、再インストールする時に、
pip uninstall paramiko
pip install --no-cache-dir paramiko
って--no-cache-dirをつけて実行してあげると、キャッシュを利用せずに再度DLして一からインストールしてくれます。