Cool little game, and great to see more people getting into Gameboy dev. Are you just using straight up uninitialised memory for the random values, or are you using it as a seed for some PRNG (like I do here: https://github.com/ekimekim/gb_necrodancer/blob/master/rng.asm)?
The other RNG approach I see a lot of games take (most infamously pokemon) is just sampling the DIV register (a fast counter), and relying on the variance in players' input timing to provide the randomness.