After trying zillion solutions like changing DNS and renewing lease, removing .plist files from Network and all other sorts of stuff. Turning off Bluetooth seems to have fixed the issue for me! I don't have much guess about why this is the case but most probably it has to do with the fact that I often use Hotspot and in the new update there is some case where it tries to reconnect to it automatically causing instability. (I'm not sure of my assumption because even when I disconnect Wifi and connect to wireless hotspot, the internet issue persists, but when I connect to USB hotspot, there is no issue at all. )