Проблема производительности с генерацией случайных уникальных чисел

У меня есть ситуация, когда мне нужно создавать десятки тысяч уникальных чисел. Однако эти цифры должны содержать 9 цифр и не могут содержать никаких 0. Мой текущий подход состоит в том, чтобы генерировать 9 цифр (1-9) и объединять их вместе, и если число уже не в списке, добавляя его в него. Например.

public void generateIdentifiers(int quantity)
{
    uniqueIdentifiers = new List(quantity);
    while (this.uniqueIdentifiers.Count < quantity)
    {
        string id = string.Empty;
        id += random.Next(1,10);
        id += random.Next(1,10);
        id += random.Next(1,10);
        id += " ";
        id += random.Next(1,10);
        id += random.Next(1,10);
        id += random.Next(1,10);
        id += " ";
        id += random.Next(1,10);
        id += random.Next(1,10);
        id += random.Next(1,10);
        if (!this.uniqueIdentifiers.Contains(id))
        {
            this.uniqueIdentifiers.Add(id);
        }
    }
}

Однако при температуре около 400 000 процесс действительно замедляется, как все больше и больше сгенерированных чисел являются дубликатами. Я ищу более эффективный способ выполнить этот процесс, любая помощь будет очень ценится.

Редактировать: - Я генерирую это - http://www.nhs.uk/nhsengland/thenhs/records/pages/thenhsnumber.aspx