Here's a simple proof using user43383's idea and a recent result of Andrew Granville: http://arxiv.org/pdf/1212.6306.pdf

According to Theorem 1 of that paper, $2^n-1$ always has a primitive prime factor $p$ that occurs to an odd exponent, except when $n=1$ or $n=6$ (where there are no primitive prime factors at all). *Primitive* here means that $2$ has order $n$ modulo $p$. In particular, $p\equiv 1\pmod{n}$. Clearly, $p \mid a_n$. So if $q_n$ denotes the smallest prime congruent to $1$ modulo $n$, then $a_n \geq q_n$ for every $n \neq 1, 6$. And in fact, by a direct check, $a_6 = 7 = q_6$, so $a_n \geq q_n$ for every $n > 1$.

Trivially, $q_n \geq n+1$ for every $n$. In fact, it is usually much larger. The simple fact that the primes have density zero implies that for every positive integer $K$, one has $q_n > Kn$  apart from a set of $n$ of density zero. (To see this, note that if this inequality fails, then one of $n+1$, $2n+1$, $\dots$, or $(K-1)n+1$ is prime, and each of these conditions puts $n$ in a set of density zero.) 

Hence: $a_n \geq n+1$ for all $n > 1$, and for every fixed $K$, $a_n > Kn$ for all $n$ outside of a set of density zero. These two facts are enough to imply that $\{a_n\}$ itself has density zero.

(Proof of the last bit: Fix $K$. Given a large $x$, if $a_n \leq x$, then the inequality $a_n \geq n+1$ forces $n \leq x$. If $n \leq x$ and $a_n \leq x$, then either $n < x/K$ or $a_n \leq Kn$. The former holds for at most $x/K$ values of $n$, and the latter holds only for $o(x)$ values of $n$, as $x\to\infty$. Thus, the number of distinct $a_n$ with $a_n \leq x$ is at most $x(1/K+o(1))$; so the upper density of $\{a_n\}$ is at most $1/K$. But this holds for all $K$.)