The weak intrinsic spin-orbit coupling in graphene can be greatly enhanced by proximity coupling. Here we report on the proximity-induced spin-orbit coupling in graphene transferred by hexagonal boron nitride (hBN) onto the topological insulator Bi$_{1.5}$Sb$_{0.5}$Te$_{1.7}$Se$_{1.3}$ (BSTS) which was grown on a hBN substrate by vapor solid synthesis. Phase coherent transport measurements, revealing weak localization, allow us to extract the carrier density-dependent phase coherence length $l_phi$. While $l_phi$ increases with increasing carrier density in the hBN/graphene/hBN reference sample, it decreases in BSTS/graphene due to the proximity-coupling of BSTS to graphene. The latter behavior results from Dyakonov-Perel-type spin scattering in graphene with a large proximity-induced spin-orbit coupling strength of at least 2.5 meV.