> Does this mean I would have to wait and average of 4.25 (worst case 8.5) minutes before my phone can connect to a new network?
No.
When a device connects to a network, it may, and usually do, send "router solicitation" multicast packet, to which the router(s) respond with "router advertisement" instantly. "Gratuitous" RAs are there to ensure that things are eventually corrected if the process did not work first time.
