Wow, EntityCrypt is full of all sorts of fun stuff.
First, the constructor creates 20 random keys if none are found in the database. Those 20 keys could never possibly be used. That loop should just be removed.
Second, getKey(String, boolean) has broken synchronization on the keyMap.get/put pair. We've been lucky that is hasn't entered into a loop inside HashMap. This is problably due to the first item above. 20 keys get stored in the map, which is enough to cause the map to not resize it's internal buckets, when later keys get requested.
Next, getRandomString() is not secure. That's the point of the SecureRandom class. This is a simple fix, however.
Also, the transaction suspending that it doesn't doesn't do the right thing if there is an OutOfMemory thrown, or other Error or RuntimeException. It really needs to do that cleanup inside a finally. Fortunately, that's what TransactionUtil.doNewTransaction is for.
Ideally, decrypt(), when it calls getKey(), shouldn't be creating new keys in the database, nor storing into the keyMap.