I know that there is an option "-Os" to "Optimize for size", but it has little affect, or even increase the size on some occasion :(
strip (or "-s" option) removes debug symbol table, which works fine; but it can only decrease only a small propotion of the size.
Is there any other way to go furthur?
If you want to squeeze every last drop of space out of your binaries, you'll probably have to learn assembly. For a very interesting (and entertaining) intro, see this link:
A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux