We observed that after a system update (.e.g. a security patch) of our cloud provider, when an impacted virtual machine (VM) reboot, it may have a second new default network gateway (in our case one VM has 10.200.0.1 as a new defaut gateway). When it happens, we observe the random slowness/timeout described.
The solution is to delete this new default gateway and keep the first one. We can do that using the following command on the VM:
route del -net 0.0.0.0 gw [FAULTY_GW] netmask 0.0.0.0 dev [NIC]
route del -net 0.0.0.0 gw 10.200.0.1 netmask 0.0.0.0 dev ens5