Finding pair of non-adjacent cliques in a dense graph
Here is one approach:


Find any 6-clique, call it $C$.
Find all vertices that aren't adjacent to any vertex in $C$.  Mark them red.
Find a 6-clique among the red vertices.


How long will this take?  Let's analyze the running time of each step.


You should be able to find a 6-clique by randomly sampling $2^{15}$ possible ways to choose 6 vertices and checking whether it forms a clique; a random collection of 6 vertices has a $1/2^{{6 \choose 2}} = 1/2^{15}$ probability of being a clique, so you're likely to find one in this way after about $2^{15}$ trials.  There are faster ways to find a 6-clique, but this will already be very fast.
This can be done in $6 \times 5000$ operations, i.e., very fast.
Now you have the problem of finding a 6-clique in a smaller graph.  How many red vertices do you expect to have?  If you pick a vertex at random, then it has a $1/2^6$ probability of being red.  Therefore, we expect about $(5000-6)/2^6 \approx 78$ red vertices.  It is very likely that a 6-clique exists among them, as there are ${78 \choose 6} \approx 2^{28}$ possible ways to choose a subset of 6 nodes, and each one has about a $1/2^{15}$ chance of being a 6-clique.  You can find a 6-clique among the red vertices in the same way as before (randomly choosing a collection of 6 red vertices and checking to see if they form a clique).  This takes about $2^{15}$ trials.


So all in all you expect this to be successful, and to take about $2^{16}$ trials, where each trial is very fast.  So this algorithm should be very fast.  There are probably ways to optimize it further, by using standard algorithms for finding a clique more efficiently than brute force, but I'd guess this should already be adequate, and it has the advantage of being easy to implement.