I recorded a simple macro and replayed it on following lines, but it seems replay speed is very slow (handle a very few lines per second). Is this expected and is there a way to improve such speed?
:set lazyredraw will greatly improve macro execution speed by not redrawing the screen while a macro is executing or a command is run other than those you type, see
:help 'lazyredraw' for more information.
Another way to reduce make sure you don't have any time wasting autocmds or mappings. If your macros are still slow after running, check your vimrc file for slow or unnecessary mappings and remove unneeded plugins. In my case I had an autocmd that would run and external program to turn off CapsLock when exiting insert mode, this was convenient and normally unnoticeable but it slowed down insert macros a lot.
If your macro enters insert mode, where you have a lot of mappings, it may help to have a key to set paste mode and disable insert mappings temporarily, see
:help 'paste' and
:help 'pastetoggle'. Keep in mind this could make insertations more difficult.
Finally, keep the macro as simple as possible by minimizing movement, mode switching, etc.