Ok so posting an answer to my question. It turned out that there was no issue with web application, app service plan, sql server or entity framework. I took a network trace of my application and 1 other application which doesn't have any issue and opened it with network monitor. We noted that they are taking different paths. After looking into the IP address we realized that the other application had a virtual network setup. You can see that by going to your app service plan and then click on Networking option in the left menu bar. And then choose the first one for vNet. Once we configured vNet, then all responses were within < 1 second.
There was one another oversight by me. The Auth0 calls were also taking 14 seconds sometimes. And when I tried running tcpping google.com from KUDU that timed out sometimes as well. But was working fine for other web applications.