乱数の幅が狭いなら(たとえばトランプなど)、一度最小値から最大値までの値が入ったリストを作っておいて、それをシャッフルするのが高速です。
重複しない乱数をつくるには
また、幅が大きいならその都度乱数を作るより仕方ありませんが、一度生成した値を Set に入れておけばリストより高速に検索できます。よく使われる手法の中では、セット、ソート済みリストのバイナリ検索、リストの線形検索の順に高速です。
連想配列を使う方法もあり、これもセットと同程度に高速ですが、特に関連付ける値がないのならセットでいいと思います。どちらも内部でハッシュを使っています。