std::random_shuffle may make use, under the hood, of random C family of functions. These functions use global state for seeds and other state.
So it is being deprecated because shuffle will do the same, but better. Namely, it uses the new <random> header from C++11 that doesn’t use global state, but its own objects making use of generators, devices and distributions.