Mathematica is a high-level language. It is much quicker and easier to implement things in Mathematica than in low-level languages like C, but it will always be much slower. I expect that the built-in method is implemented in a low-level language.

EdgeAdd is necessarily slow because for each added edge, it creates an entirely new graph. Even if you work in a low-level language, e.g. even if you would use the equivalent C function when working with the igraph C library, performance would be bad for similar reasons.

To obtain good performance, you would need to modify the graph in-place, and use a representation that can handle the operations you need efficiently, e.g. adding an edge should not trigger memory reallocation. Degrees should also be updated as you add edges, and not recomputed at every step.

For example, as a start, you could represent the graph with an adjacency matrix that already has all nodes you plan to add, but they are unconnected. Then update the matrix in-place as you add each edge.

n = 100;

am = ConstantArray[0, {n, n}];

am[[1, 2]] = am[[2, 1]] = 1;

Do[
 v = RandomChoice[Total[am] -> Range[n]];
 am[[v, k]] = am[[k, v]] = 1;
 ,
 {k, 3, n}
 ]

AdjacencyGraph[am]

I chose this method because it is both easy to implement in Mathematica, fast, and I believe even Compileable in Mathematica. But it is far from the best method. The memory requirements are $O(n^2)$. You could improve on it, but that would take more work.

If you look at how libraries like igraph implement various graph algorithms, you will see that they typically work with the representation that is best for each particular task. They often do not work with their graph data structure directly. Instead, they convert it to a suitable form, process it, then convert it back.