Thanks for the answer, Ashley.
I did some testing and figured out that it has something to do with the APK size. For a small test APK, it works really quick as supposed. For a big project (~ 50 MB), it's slow somehow. Disabling 'Minify script' helped a bit, too.
Interesting fact: The same problem and solution occurs for the official Google Play plugin, too.
For the moment, I'm fine with this, as I won't publish the full sized APK anyway. I might provide a bug report once I have time.