Russia earned their paranoia the hard way - Napoleon and Hitler. They remember an invader that reached Moscow, took it, and held it for weeks, then burned it on the way out. They remember another invader that came within 35 miles of Moscow. That invasion started from the middle of Poland; they don't want to face one that starts from the eastern edge of Ukraine.
Of course, this is still paranoia, no matter how honestly they come by it. NATO is not Hitler, nor is it Napoleon. NATO is not going to launch an unprovoked invasion of Russia, no matter what happened in the previous two centuries.
But when Ukraine talks about joining NATO, Russia feels the gun pointed at it. There is no gun, but Russia feels it.