Yes I have allegro 5, and I do list every package in the gcc command (you're right, that was a pain, but since I use a makefile, it doesn't matter much).
I installed it by following the debian tutorial here.
EDIT: I used your command but linking every addon instead of the monolith, and tried to execute the file on a another computer without allegro, but it didn't work.
It gave me this error:
./tetris: error while loading shared libraries: liballegro_primitives.so.5.0: cannot open shared object file: No such file or directory
It still is dynamically linked, which I'm guessing is because I only have the .so versions of the library and the source.
Also, I tried to recompile allegro with "-DWANT_MONOLITH=on" to get the monolith version, but it was just ignored by cmake.