Just some ideas:
Have you tested it outdoors? GPS works best with a clear view of the sky.
You wrote:
I have tried every setting to resolve this issue. From Apps --> Sandboxed Play services settings. Standard Server instead of Graphene Server in location setting, but no result.
If I have understood correctly, you have already experimented with the Sandboxed Play Services Settings.
Did you follow all these steps (I quote from https://grapheneos.org/usage#sandboxed-google-play-configuration)
If you want to use Google's network location service to provide location estimates without satellite reception, you can disable the "Reroute location requests to OS APIs" toggle and grant what it requires to provide network location. You will need to grant "Allow all the time" Location access to Google Play services along with the Nearby Devices permission for it to have all the access it needs. You need to use the "Google Location Accuracy" link from the sandboxed Google Play configuration menu to access the Google Play services menu for opting into their network location service, otherwise this is all pointless.
Have you enabled in Settings> Location> Secure User Plane Location (SUPL) and Predicted Satellite Data Service (PSDS)?
An excerpt from the GrapheneOS documentation:
If you have both cellular connectivity and Location enabled, A-GNSS is used in addition to PSDS Control Plane and/or User Plane (SUPL) to significantly reduce the time it takes GNSS to obtain an initial location fix. These receive rough location information from a server based on nearby cell towers.
You can find more information here:
https://grapheneos.org/faq#other-connections
Do Google Maps and the other apps that are experiencing problems have permission to access location?
You can check this by long pressing the app icon App info> App permissions.