現状のバランスのまま、攻撃技の順番だけを完全にランダムにしてしまったら
もちろん難易度が跳ね上がるだけだと思いますし、そんなものはおっしゃるとおりただの運ゲーです。

ですから、完全にランダムにするのではなく
たとえば、激震のすぐあとに激震はこない、もしくは確立を極端に低くする、とか
ランドスライドのあとは必ずマウンテンバスターがくる、など一定のパターンや法則性をもたせり残すことで
プレイヤーは、つぎはあの攻撃がくる確率が高い、などあるていど予測して動くことができるようにし
また、危険な技ほど予備動作を長くして、とっさに対処する猶予を与えるなどの調整も必要だと思います。

完全な覚えゲーの問題点は、難易度そのものよりも
覚えたあとに飽きやすい、ということと、初心者と熟練者のあいだで差が大きくなること、だと思います。