You can do these following things:
1. Try to remove unused header files.
2. Try to use shared libraries instead of static libraries. (I am assuming you know the difference between these two)
3. Not the least use gcc with optimization option i.e (-O , -O1, -O2, -O3 or -Os) capital O not zero.
I would suggest to with -Os option.
"gcc -Os program_name.c"
Compile your code with and without -O option, and you will see the size differences between these two.