I assume you use Android Auto?
Your car navigation has noting to do with using Android auto. Two independent platforms.
It looks like communication between your phone and car's unit is not working properly. I do not think you need any cell connection in your phone to use Google maps From the phone as they can be used while off-line.
Did this connection ever worked properly or it is recent occurrence?