I think it's a problem with Android, it's just not very fast at decoding audio. IIRC I remember a Chrome engineer saying the Android media APIs weren't great which meant long decode times sometimes.
There's not much you can do other than either preload everything and wait it out, or don't preload on startup and use the 'preload' action to try and get the few most important sounds preloaded in advance of whenever they'll be needed.