After a lot of trial an error I finally cracked it.
Using a combination of gifsicle, XnView, grafx2 and finally this on the Amiga: https://www.sundin.nu/amiga/
It plays quite nice in DeluxePaint IV AGA. File size is 161 KB. I think quite long animations and also with more moving parts could work.
Now that I have a process for this I could to some other ones.