Assuming you're referring to the signing of APT repositories, which is usual, and not to signing individual packages, which is not, then the answer is that APT uses gpgv, and therefore supports all the algorithms that that binary does. Since gpgv is part of GnuPG, it should support all the relevant algorithms the equivalent version of GnuPG does.
Therefore, assuming you have a suitable version of gpgv, you can indeed use EdDSA algorithms. That appears to be new in GnuPG 2.1.0, so that should be stretch or newer. Note that the dependencies do permit the use of v1 of gpgv, which wouldn't support that, but that would be a bizarre configuration.
In general, you should aim for at least a 128-bit security level. That means that if you're using RSA or DSA, it should be at least a 3072 bit key (which is the max for DSA), or you should use a 256-bit or larger elliptic curve. Unlike SSH, where DSA is practically limited to 1024 bits and is therefore insecure, DSA is not insecure in OpenPGP, but it has fallen out of favor in the cryptographic community because it is slower than most EC algorithms.
You should also be sure that your signatures are made with SHA-256 or SHA-512. SHA-1, which used to be the default, is insecure for signatures and APT will no longer accept it (and you wouldn't want to do so even if it did).
RSA is currently the default for historical reasons and the fact that EdDSA hasn't been standardized as part of OpenPGP yet. However, unless you need to interoperate with other, non-GnuPG implementations, there's no reason not to use EdDSA.
