Location update takes a long time after reboot, using FusedLocationProviderClient

Question

I'm using the FusedLocationProviderClient to access the lastLocation of the user. If it's null, I'm waiting for requestLocationUpdates to return.

I've tested this on my Pixel 3a by rebooting the device, which clears the last location, however it takes >2 mins to return a location.

Here's my code. What am I doing wrong?

    private fun onLocationPermissionGranted() {
        val fusedLocationProviderClient = LocationServices.getFusedLocationProviderClient(
            requireContext()
        )

        fusedLocationProviderClient.flushLocations()

        Log.i("Jamie", "Attempting to access last location")

        val locationRequest = LocationRequest.create()
        locationRequest.priority = LocationRequest.PRIORITY_BALANCED_POWER_ACCURACY
        locationRequest.interval = 5000
        locationRequest.numUpdates = 1

        val callback = object : LocationCallback() {
            override fun onLocationResult(locationResult: LocationResult?) {
                Log.i("Jamie", "Calling location permission granted again")
                onLocationPermissionGranted()
            }
        }

        fusedLocationProviderClient.lastLocation
            .addOnSuccessListener { location: Location? ->
                Log.i("Jamie", "FusedLocation onsuccess called")
                if (location == null) {
                    Log.i("Jamie", "location null")
                }

                location?.let {
                    fusedLocationProviderClient.removeLocationUpdates(callback)
                    Log.i("Jamie", "Location received")
                    this.map.isMyLocationEnabled = true
                    viewModel.currentLocation = location
                    updateCamera(location.latitude, location.longitude)
                }
            }

        fusedLocationProviderClient.requestLocationUpdates(locationRequest, callback, Looper.getMainLooper())
    }

2020-08-31 14:04:33.834 3780-3780/com.redacted I/Jamie: Attempting to access last location
2020-08-31 14:04:34.547 3780-3780/com.redacted I/Jamie: FusedLocation onsuccess called
2020-08-31 14:04:34.547 3780-3780/com.redacted I/Jamie: location null
2020-08-31 14:06:50.404 3780-3780/com.redacted I/Jamie: Calling location permission granted again
2020-08-31 14:06:50.404 3780-3780/com.redacted I/Jamie: Attempting to access last location
2020-08-31 14:06:50.517 3780-3780/com.redacted I/Jamie: FusedLocation onsuccess called
2020-08-31 14:06:50.517 3780-3780/com.redacted I/Jamie: Location received