You could add the download only flag to apt, you will get a .deb file which in fact is an archive you can extract. just place the gksudo file in there in your /usr/bin/ dir.
I am also pretty sure that this lag is caused by your theme. I saw that before on "everything" and terminologie: Specific theme causing a specific lag of fixed time on specific hardware regardless of specs and load (not reproducable on other maschines).
On my case "everything" lags exactly a half second on amd fx cpus when the bodhi theme is loaded.
Why? Magic i assume.
Try to change your theme.
As drop down terminal I use Guake. But my question was for the graphical sudo esudo, as starting GUIs from terminal is discouraged: "You should never use normal sudo to start graphical applications as root."
The difference of sudo and gksudo is that gksudo stops programs from writing in your /home and thus protects your config files. In real live it makes absolutely zero difference unless you want to start a web browser as root, but really you have greater problems than config files if you do so.