I don’t know Java, but I had the same kind of problem when coding with Free Pascal.
I discovered that all the newing of trie nodes was relatively slow. So now when I use a trie, I create a static array of trie nodes, and allocate the elements of that array instead of newing them. I just keep a variable with the last used index.
YMMV.