There is an algorithm for computing $F(N) = \# \{ (a,b) : 1 \leq a, b \leq N, \gcd(a,b) = 1 \}$ in time $O(N^{5/6 + \epsilon})$. This relies on the algorithm of Deleglise and Rivat (see their paper here) that computes $M(x) = \sum_{n \leq x} \mu(n)$ in time $O(x^{2/3} (\log \log x)^{1/3})$.
The idea is to use
$$
F(N) = \sum_{a=1}^{N} \sum_{b=1}^{N} \sum_{d | \gcd(a,b)} \mu(d) = \sum_{d=1}^{N} \mu(d) \left\lfloor \frac{N}{d}\right\rfloor^{2}.
$$
Now, break this sum up into the terms with $1 \leq d \leq N^{\alpha}$ and the terms with $N^{\alpha} < d \leq N$. The first term
$$
\sum_{d=1}^{N^{\alpha}} \mu(d) \left\lfloor \frac{N}{d} \right\rfloor^{2}
$$
can be computed easily in time $O(N^{\alpha + \epsilon})$, since all $\mu(d)$ for $d \leq N^{\alpha}$ can be computed in time $O(N^{\alpha} \log \log(N))$ (see this preprint). For the range $N^{\alpha} < d \leq N$, let $k = \lfloor N/d \rfloor$. We get the sum
$$
\sum_{k=1}^{\lfloor N^{1-\alpha} \rfloor} k^{2} \sum_{\substack{e \\ \lfloor N/e \rfloor = k}} \mu(e) = \sum_{k=1}^{\lfloor N^{1-\alpha} \rfloor} k^{2} (M(b_{k}) - M(a_{k})).
$$
Here $a_{k}$ and $b_{k}$ are the smallest and largest positive integers $N$ for which $\lfloor N/e \rfloor = k$, respectively. There are $O(N^{1-\alpha})$ terms in the sum above, and each can be computed in time $O(N^{2/3+\epsilon})$. The total running time $O(N^{\alpha + \epsilon} + N^{5/3 - \alpha + \epsilon})$ is minimized when $\alpha = 5/6$ and gives $O(N^{5/6 + \epsilon})$.
