What is gssapi-with-mic?

Solution 1:

Message Integrity Code.

This is also called a Message Authentication Code, but that acronym gets used for other things, so MIC is less ambiguous. From that Wikipedia page:

The term message integrity code (MIC) is frequently substituted for the term MAC, especially in communications, where the acronym MAC traditionally stands for Media Access Control.

Solution 2:

The fix is simple: disable attempts to use GSS-API by adding the following to ~/.ssh/config:

GSSAPIAuthentication no