Getting random coordinates on a rectagle without overlapping

I have a very big rectangle (100,000 x 100,000) and i am trying to position a lot of circles with different sizes randomly on it. My current solution is to store all previously used coordinate pairs in a map and then randomly generate a new pair and check if it exists in the map.

func randomCoords(xCoordinateMap map[int]bool, yCoordinateMap map[int]bool, radius int) (int, int) {
    x := rand.Intn((width-radius)-radius) + radius
    y := rand.Intn((height-radius)-radius) + radius

    for xCoordinateMap[x] && yCoordinateMap[y] {
        x = rand.Intn((width-radius)-radius) + radius
        y = rand.Intn((height-radius)-radius) + radius
    }

    xCoordinateMap[x] = true
    yCoordinateMap[y] = true

    return x, y
}

Because i'm generating a lot of coordinates, this method can get a little slow. Is there a better and most importantly faster way of getting random coordinates on a rectangle and maybe also a way to get them without the circles overlapping?