Can't SSH for 5 minutes+ after boot up

Question

I'm running Mojave 10.14.6 on a new MacBrook Pro and whenever my mac is completely off and then comes back on, it seems to take at least 5 minutes to be able to connect or access anything over ssh. The first time it happened, I thought the credentials had been changed, but I'm glad I waited because after multiple attempts with the same credentials, it worked. This has happened a few more times, if my laptop dies or it runs an update and restarts. It's especially frustrating when I'm ready to start working for the day and when it finally does reconnect, all of the files I was in before get closed out.

If I ping the ip, it responds, but if I try and ssh from the terminal, the "connection is refused" -- it doesn't even give me the option to enter a password. If I try and go through my usual interface (Coda) to connect to the server/database, it gives me a similar error, something like "connection failed". I don't believe it's a Coda problem as I've used it on other macs just fine and it also threw and error in the terminal.

Has anyone else had this problem, or does anyone know what could be causing this?

Edit: Added updated info

I believe the previous photo I posted was incorrect, I think the result of the command must have been right after I was re-connected. The above photo is the correct one.

Here are the results that @FrancisfromResponseBase asked for, though I'm not sure when exactly the connection re-opened, so while I was hurridly running through the commands, it may have re-connected before I realized. I'll try to double check the next time it happens to better pinpoint it and to make sure I'm getting the right results for the before commands I run:

Not working/Before:

Working/After:

Answer 1

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.