There are several levels of buffering. When you press Ctrl+C, this stops the program from emitting data to the terminal. This doesn't affect data that the terminal emulator hasn't displayed yet.
When you're displaying data at very high speed, the terminal can't keep up and will lag. That's what's going on here: displaying text is at lot more expensive than producing these random numbers. Yes, even with a bitmap font — producing cryptographic-quality random numbers is dirt cheap in comparison. (I just tried on my machine and the X process saturated the CPU, with xterm taking a few % and cat (which the random number generation is accounted against) barely reaching 1%. And that's with a bitmap font.)
If you want this to just stop now, kill the terminal emulator. If you don't wish to do that, at least minimize the window; intelligent terminal emulators (such as xterm) will not map the window, which saves the X CPU time, so the garbage will finish displaying quicker. The X server has high priority, so this will make a big difference to your machine's responsiveness while xterm is processing the data in the background.
When all this is going on in a remote shell, the lag is even worse, because the data produced by cat has to first go through the SSH connection. Your press of Ctrl+C also has to go through the SSH connection; it gets somewhat higher priority (it's sent out of band), but that still takes some time during which more output accumulates. There's no way to suppress data in transit short of closing the SSH connection (which you can do by pressing Enter then ~.).