Lo and behold, it turned out to be related to the seeding of the random number generator in Java. Normally this is linked to /dev/random but can be sped up by using /dev/urandom, which uses some entropy of your system. Still, the urandom device, while faster, still caused a 20-fold difference.
As a workaround, you can tell your JVM which seed generator to use and prevent JVM from waiting or looking or whatever it does. See also the JAAS Reference Guide for more information.
If you call your JVM with the command line switch
it will go much speedier! And yes, there is a dot "." inside that path, in order to work around another bug. :)