It turns out, banknotes in the form we are used to were introduced as early as in 1995. But that was before the devaluation of the ruble in 1998, so all the bills had three additional zeros. There were no 5,000,000 ruble bills back then (the modern "habarych" was only drawn in 2006), but it's nice to look at those 5,000 rubles, the face value of which is comparable to the later 5 rubles.
I don't remember such money at all. But I do remember the 1993 banknotes, they were in circulation, and for the blue 100 rubles you could buy a box of matches.
Ah, those were the days.