The last windows I used was XP. But accelerators do work in Linux.

And they are not just about menus: in any modal window I can do Alt+O for Ok. And this paradigm allows discoverability, I don't need to memorize shortcuts, I just hold Alt and look for underscored letters – that's how GUI should be IMO.

It's not perfect, and if I were designing UI from scratch, I'd made this feature modal instead of allocating entire physical key for that (like they do hints in vim-like browsers).