Can't SSH for 5 minutes+ after boot up
My friend, I suggest that we examine the routing table in a 'before / after' manner: before the problem occurs; after the problem has occurred.  

Could you kindly post the output of the following before and after the behavior occurs:

sudo netstat -nr 


I assume from looking at the ssh debug you posted that you are ssh'ing to the ip address, and not a hostname.  Is this correct?  If not, then we should look at the domain name resolution.  

sudo scutil --dns


as well as 

sudo cat /etc/resolv.conf


would help in this case.  

Lastly, let's rule out any egress filtering on the firewall.  It is a lot of information, but better that we have the full perspective, from rules to NAT to timeouts and states:

sudo pfctl -vvv -sa


F.