The characteristic polynomial of a matrix $M$ can be written as
$\chi_M(z) = z^n + \textrm{trace(M)}z^{n-1}+\ldots + \det(M)$.
Since you know ahead of time that all the entries of $M$ are rational, you can be assured that $\det(M)$ is rational; say $\det(M) = p/q$. Now, the rational roots theorem assures you that, provided $\chi_M$ has a rational root $\lambda = k/l$, then $k$ divides $p$ and $l$ divides $q$. But, you know ahead of time (somehow) that all eigenvalues of $M$ are rational.
You can compute the determinant of $M$ much faster than the full characteristic polynomial by computing the LU-factorization of $M$. Since all the entries are rational, the entries of the triangular factors are also rational; you would of course have to ensure that the factorization is done symbolically so that the determinant is also computed exactly.
Trying all rational numbers $k/l$ such that $k | p$ and $l | q$ is also prohibitively expensive. However, you could use a conventional eigensolver to get a set of approximate eigenvalues $\hat{\lambda}_1,\ldots,\hat{\lambda}_n$, then look for the exact, rational eigenvalues with the desired divisibility properties nearby to each approximate one.
A cursory Google search didn't turn up anything for the exact eigendecomposition of rational matrices, so I doubt that anyone has written a program to do this before. However, you might have luck with the linear algebra features of sympy.