A cladogram is an unrooted tree with labeled leaves and unlabeled internal branchpoints of degree $3$. Aldous has studied a Markov chain on the set of $n$-leaf cladograms in which each transition consists of removing a random leaf and its incident edge from the tree and then reattaching the leaf to a random edge of the remaining tree. Using coupling methods, Aldous has shown that the relaxation time (i.e. the inverse of the spectral gap) for this chain is $O(n^3)$. Here, we use a method based on distinguished paths to prove an $O(n^2)$ bound for the relaxation time, establishing a conjecture of Aldous.