Order by random() on Redshift is horribly slow

So we have a database of 100 million records and our queries are running very fast on redshift, until we have to select random records. We are using " order by random()".

The largest set of records we might need a random sample of is 10 million.

Can someone please help me speed up this randomization process? Thanks in advance.