Grade Build takes much longer than old Internal build system

I recently upgraded to Unity 2018.3 and I think in the process the default Build System changed from (now deprecated) Internal(Old) to Gradle(New) build system. Simple prototype projects take forever to build with Gradle. I tested both build systems on the same project and where old Internal build system takes 30 seconds to 1 minute to build, Gradle Build system takes 10 to 30 minutes.

Most of that time Gradle build is stuck at validateSigningRelease task.

Sure I could just switch to the old Internal build system for every prototype I work on, but that is annoying. And since Unity has deprecated the old Internal build system, they might completely remove that option in the near future.

Has anyone else experienced the same problem? Or knows what could be causing this behavior?