Thanks for your help guys, I really appreciate it!

Update:

I randomly thought of a method that allows me to create a short list of faces to test intersection each frame, instead of testing all faces in the terrain(O(N)) on every frame.

With my method, I was able to narrow down the amount of intersection tests from the original 33000(all terrain faces) to ~100 each frame, which is quite manageable and resolved the FPS issue.

In computational complexity, I was able to reduce intersection tests from O(N)->O(sqrt(N)).

In other words, you implemented a O(log n) solution a la spatial subdivision?