How to create unique string containing numbers and letters without repeating name once used

I'm attempting the following coding challenge in C#:

Manage robot factory settings.

When a robot comes off the factory floor, it has no name.

The first time you turn on a robot, a random name is generated in the format of two uppercase letters followed by three digits, such as RX837 or BC811.

Every once in a while we need to reset a robot to its factory settings, which means that its name gets wiped. The next time you ask, that robot will respond with a new random name.

The names must be random: they should not follow a predictable sequence. Using random names means a risk of collisions. Your solution must ensure that every existing robot has a unique name.

I've created a Robot class which passes 7 of my 8 unit tests. The one failing is:

[Fact]
public void Robot_names_are_unique()
{
    const int robotsCount = 10_000;
    var robots = new List<Robot>(robotsCount); // Needed to keep a reference to the robots as IDs of recycled robots may be re-issued
    var names = new HashSet<string>(robotsCount);
    for (int i = 0; i < robotsCount; i++) {
        var robot = new Robot();
        robots.Add(robot);
        Assert.True(names.Add(robot.Name));
        Assert.Matches(@"^[A-Z]{2}\d{3}$", robot.Name);
    }
}

I walked through my code and I believe the issue is because I'm generating random values but I'm not ensuring the values are unique when creating many names. Here's my class:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Robot
{
    Random random = new Random();
    Dictionary<string, bool> usedNames = new Dictionary<string, bool>();
    public Robot()
    {
        Name = RandomName();
    }

    private string _name;

    public string Name
    {
        get { return _name; }
        set { _name = value; }
    }


    public void Reset()
    {
        Name = RandomName();
    }

    private string RandomName()
    {
        Random rand = new Random();
        int nums = random.Next(000, 1000);
        var val = nums.ToString("000");
        const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        string letters = new string(Enumerable.Repeat(chars, 2)
            .Select(s => s[random.Next(s.Length)]).ToArray());
        string name = $"{letters}{val}";
        if (usedNames.ContainsKey(name))
        {
// Implement here or refactor with loop?
        }
        return name;
    }
}

However, after reviewing my code, I feel like there is a better approach. I was thinking the approach would involve iterating through the possible numbers and letters in the name sequentially from start to finish to ensure that each name is unique. Am I on the right track? What could I do better?