Check for entries in Pi-hole's Query Log while this is happening. If Pi-hole is blocking domains that are needed then you'll see them in here.
Some Android OSs screw around with your DNS settings and add their own. Previous posts about this here.
Please don't auto update Pi-hole. Instead review the announcements of new releases and determine how or if they affect you, and plan your update.
That would suggest that the problem lies outside of Pi-hole. For example if the Pi-hole is connected via wifi and the signal to it is poor, it may be struggling to talk on the network, causing clients to wait longer. Make sure it has a good wifi signal or switch it from wifi to ethernet (and do a Reconfigure, a search will find how to do this).
By all means submit a debug log if you would like the config inspecting for any issues.