Eu tenho exatamente o mesmo problema, embora minha diferença seja de 10 segundos.
Sep 12 13:38:28 jumbo NetworkManager[1139]: <info> (wlan2): supplicant interface state: disconnected -> scanning
Sep 12 13:38:38 jumbo wpa_supplicant[1715]: wlan2: Trying to associate with 00:15:c7:29:86:81 (SSID='MILANO' freq=2412 MHz)
Infelizmente, não consegui encontrar nenhum documento sobre os diferentes estados da interface, por isso só posso adivinhar o que significa o estado "scanning": o seu computador ouve outros pontos de acesso com o mesmo SSID e liga-se ao AP com o melhor sinal qualidade.
Portanto, acredito que esse problema poderia ser resolvido, se pudéssemos definir uma entrada estática e controlar por meio do qual o AP seu computador deveria se conectar, isso pelo menos seria uma solução para seu local de trabalho / casa, etc ... Até onde eu sei, a nmcli não oferece essa opção agora, já que você só pode saber a qual SSID você deseja se conectar. Isso pode ser roteirizado e usado como um cronjob:
sudo nmcli device wifi connect "${SSID}" iface "${iface}"
Outra solução pode modificar a duração dessa lacuna irritante para um valor muito menor, mas duvido que esse valor seja configurável agora.