Right, but pseudo-randomness is still monadic because you are mutating the state of the random number generator. That it is in IO is an implementation detail of where that generator's state lives.

It's been a little while since I worked with Haskell but I'll surprised if nobody ported e.g. Mersenne Twister to it, complete with its own Random monad. If not, maybe that could be a new project...

You have to get the randomness out of IO, because referential transparency and randomness of any kind (psuedo or otherwise) are fundamentally in opposition, but once you have the random source in hand, you can use it any way you like in otherwise pure code. The Random support in Haskell is set up to permit and to some extent support this usage, with the ability to "split" a random generator into something you use now and something you pass along. After that it's your responsibility to properly split & use, but I haven't yet found it to be a big problem in practice.