1. Зачем каждый раз конструировать Random? Делайте это один раз.
2. Вот вся эта кракозябра в for - она как то не попадает под описаное вам в алгоритме. Судя по всему вы зачем то пытаетесь сгенерировать число на основе словаря. Вангую что вот именно эта часть приводит к диким тормозам.
3. Можно использовать не list, а hashset (вроде) - поиск по нему намного быстрее.
4. Лучше в контейнере держать не строку, а все таки число если это возможно - сравнение строк - долгая операция может быть